桶排序

桶排序流程：

桶排序是将数列拆分放到n个桶中，然后每个桶再对自己内部的元素进行排序（使用其他排序算法），然后再把每个桶内的有序数列合并起来

比如数组[4,2,5,6,1,2,5,6,7]，把13放到第一个桶里，46放到一个桶里，7放到一个桶里，然后三个桶分别各自排序，最后合并

如下图：

桶排序有几个要点：

• 桶排序是用空间换时间，合理设置桶数量
• 尽量让元素均匀分布在各个桶中

代码示例：

public class Bucket {

    /**
     * 桶数量
     */
    private static final int BUCKET_SIZE = 3;

    public static void main(String[] args) {
        int[] array = {4, 2, 5, 6, 1, 2, 5, 6, 7};
        System.out.println(Arrays.toString(bucketSort(array)));
    }

    public static int[] bucketSort(int[] array) {

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < array.length; i++) {
            min = Math.min(min, array[i]);
        }

        List[] buckets = new ArrayList[BUCKET_SIZE];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<Integer>();
        }

        // 每个元素放到对应的桶里
        for (int i = 0; i < array.length; i++) {
            int bucketIndex = (array[i] - min) / BUCKET_SIZE;
            buckets[bucketIndex].add(array[i]);
        }

        int[] results = new int[array.length];
        int index = 0;
        // 遍历所有桶
        for (int i = 0; i < buckets.length; i++) {
            Object[] tmpArray = buckets[i].toArray();
            // 桶里的元素使用其他排序算法排序
            Arrays.sort(tmpArray);
            // 排序后按顺序填到结果数组中
            for (int j = 0; j < tmpArray.length; j++) {
                results[index++] = (int)tmpArray[j];
            }
        }

        return results;
    }
}